Change tag url structure

Is it possible to change this example.com/tag:travel to this example.com/?tag=travel?

Grav does fully support the traditional URL queries, however any plugins and/or themes would need to be modified to look for a query value rather than a parameter as it's doing now.

Could you provide an example for TwentyFifteen Site skeleton/theme? I'm new to coding in general so I'm having hard time finding the part which I have to edit.

This is not a trivial change. Your basically wanting to change how data is transferred between pages. Unless you have a good reason, I suggest that you leave the parameter style as it's prettier and works fine as-is.

Search engines do not seem to support the default format so I want to change it to be compatible with this: https://support.google.com/webmasters/answer/6080550?hl=en and this https://www.bing.com/webmaster/help/ignore-url-parameters-d7496c65 Would appreciate any hints which part I need to edit to make this work :)

The great thing is that search engines will treat the Grav parameters as part of a valid independent URL. So there's no need for query support. This is not something you need to worry about.